﻿using System;
using System.Collections.Generic;
using Pagination.RangeCollector;

namespace Pagination.Storage
{
    public class AvlStorage : IStorage
    {
        private readonly IRangeCollector collector;
        private readonly Stack<Tuple<AvlNode, bool>> stack = new Stack<Tuple<AvlNode, bool>>();
        private readonly AvlTree storage = new AvlTree();

        public AvlStorage(IRangeCollector collector)
        {
            this.collector = collector;
        }

        #region IStorage Members

        public void Add(int item)
        {
            storage.Insert(item);
        }

        public void Range(int left, int right)
        {
            stack.Clear();
            var aLength = right - left + 1;
            var i = 0;
            GetNodeByIndex(left - 1, stack);

            while (stack.Count != 0)
            {
                if (i == aLength)
                    break;
                var node = stack.Pop();
                collector.Append(node.Item1.Value);
                i++;
                if (node.Item1.Right != null)
                {
                    var end = stack.Count;
                    stack.Push(new Tuple<AvlNode, bool>(node.Item1.Right, false));
                    while (i < aLength && stack.Count != end)
                    {
                        var llnode = stack.Pop();
                        if (llnode.Item2)
                        {
                            collector.Append(llnode.Item1.Value);
                            i++;
                            continue;
                        }
                        var c = i + (llnode.Item1.Left == null ? 0 : llnode.Item1.Left.Count);

                        if (llnode.Item1.Right != null && c < aLength)
                            stack.Push(new Tuple<AvlNode, bool>(llnode.Item1.Right, false));
                        if (llnode.Item1.Left != null)
                        {
                            stack.Push(new Tuple<AvlNode, bool>(llnode.Item1, true));
                            stack.Push(new Tuple<AvlNode, bool>(stack.Peek().Item1.Left, false));
                        }
                        else
                        {
                            collector.Append(llnode.Item1.Value);
                            i++;
                        }
                    }
                }
            }
            collector.End();
        }

        #endregion

        private void GetNodeByIndex(int index, Stack<Tuple<AvlNode, bool>> stack)
        {
            var current = storage.GetRoot();
            for (;;)
            {
                var leftCount = current.Count;

                if (leftCount > index)
                {
                    stack.Push(new Tuple<AvlNode, bool>(current, false));
                    current = current.Left;
                }
                else if (leftCount == index)
                {
                    stack.Push(new Tuple<AvlNode, bool>(current, false));
                    return;
                }
                else
                {
                    index -= leftCount + 1;
                    current = current.Right;
                }
            }
        }
    }
}